/*
 * 0046. Majority Element
 * 给定一个整型数组，找出主元素，它在数组中的出现次数严格大于数组元素个数的二分之一。
 * https://www.lintcode.com/problem/majority-element/description
 * 
 * 样例
 * 给出数组[1,1,1,1,2,2,2]，返回 1
 * 
 * 挑战
 * 要求时间复杂度为O(n)，空间复杂度为O(1)
 *  
 * 2018.06.23 @jeyming
 */
package majority_element_0046;

import java.util.Collections;
import java.util.List;

public class Majority_element_0046 {
	/*
	 * @param nums: a list of integers
	 * @return: find a  majority number
	 */
	public int majorityNumber(List<Integer> nums) {
		// write your code here
		Collections.sort(nums);
		int numsCnt = nums.size() / 2;
		int cnt = 1;
		int tmp = nums.get(0);
		for(int i = 1; i < nums.size(); ++i) {
			if(tmp == nums.get(i)) {
				++cnt;
			} else {
				cnt = 1;
				tmp = nums.get(i);
			}
			if(cnt > numsCnt) {
				return tmp;
			} 
		}
		return 0;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
